[Leetcode单排] 树类题目集合1 (N102 N107 N429 N872 N112 N113)

tree

字数统计: 1.3k阅读时长: 7 min

 2019/08/10  Share

102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

层次遍历，但是题目需要把每一层的放到一个 List 里面，这里用的是计数（需要注意先把左右节点放到队列中再进行数量判断）。当然也可以使用在 while 最开始获取队列中的 size 作为这一层的大小，之后里面加一层 for 循环，详见此。

public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> result = new ArrayList<>();
       if (root == null) {
           return result;
       }
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       int count = 1, temp = 0, next = 0;
       List<Integer> layer = new ArrayList<>();
       while (!queue.isEmpty()) {
           TreeNode node = queue.poll();
           int val = node.val;
           layer.add(val);
           if (node.left != null) {
               queue.offer(node.left);
               next++;
           }
           if (node.right != null) {
               queue.offer(node.right);
               next++;
           }
           if (++temp == count) {
               result.add(new ArrayList<>(layer));
               layer.clear();
               count = next;
               next = 0;
               temp = 0;
           }
       }
       return result;
   }

107. Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

这道题就很没意思了，每次只要加在 List 的最前面就可以了。

public List<List<Integer>> levelOrderBottom(TreeNode root) {
      List<List<Integer>> result = new LinkedList<>();
      if (root == null) {
          return result;
      }
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      int count = 1, temp = 0, next = 0;
      List<Integer> layer = new ArrayList<>();
      while (!queue.isEmpty()) {
          TreeNode node = queue.poll();
          int val = node.val;
          layer.add(val);
          if (node.left != null) {
              queue.offer(node.left);
              next++;
          }
          if (node.right != null) {
              queue.offer(node.right);
              next++;
          }
          if (++temp == count) {
              result.add(0, new ArrayList<>(layer));
              layer.clear();
              count = next;
              next = 0;
              temp = 0;
          }
      }
      return result;
  }

429. N-ary Tree Level Order Traversal

https://leetcode.com/problems/n-ary-tree-level-order-traversal/

依然是层次遍历，只不过二叉树换成 N 叉树。

public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    int count = 1, temp = 0, next = 0;
    List<Integer> layer = new ArrayList<>();
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        int val = node.val;
        layer.add(val);
        if (node.children != null && node.children.size() !=0) {
            for (Node n : node.children) {
                queue.offer(n);
                next++;
            }
        }
        if (++temp == count) {
            result.add(new ArrayList<>(layer));
            layer.clear();
            count = next;
            next = 0;
            temp = 0;
        }
    }
    return result;
}

872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/

判断两颗二叉树的叶子节点（从左到右）是否相等。这里用的比较常规做法，使用中序遍历，把打印换成判断是否为叶子节点。

public boolean leafSimilar(TreeNode root1, TreeNode root2) {
      if (root1 == null && root2 == null) {
          return true;
      }
      if (root1 == null || root2 == null) {
          return false;
      }
      List<Integer> leaves1 = getLeaves(root1);
      List<Integer> leaves2 = getLeaves(root2);
      return leaves1.equals(leaves2);
  }

  private List<Integer> getLeaves(TreeNode node) {
      List<Integer> list = new ArrayList<>();
      inorder(node, list);
      return list;
  }

  private void inorder(TreeNode node, List<Integer> list) {
      if (node == null) {
          return;
      }
      inorder(node.left, list);
      if (node.left == null && node.right == null) {
          list.add(node.val);
      }
      inorder(node.right, list);
  }

112. Path Sum

https://leetcode.com/problems/path-sum/

这里的递归没有去判断是否为 null ，因为为 null 的情形本身就被排除了。（另外，此类是否存在一个满足条件的问题，当有情况成功时，需要立刻返回。总是遗漏掉 if 为 true，立刻返回的情形。）

public boolean hasPathSum(TreeNode root, int sum) {
     if (root == null) {
         return false;
     }
     return dfs(root, 0, sum);
 }

 private boolean dfs(TreeNode node, int curSum, int target) {
     if (node.left == null && node.right == null) {
         return target == curSum + node.val;
     }
     if (node.left != null) {
         if (dfs(node.left, curSum + node.val, target)) {
             return true;
         }
     }
     if (node.right != null) {
         if (dfs(node.right, curSum + node.val, target)) {
             return true;
         }
     }
     return false;
 }

别人写的更精炼

public boolean hasPathSum(TreeNode root, int sum) {
    if(root == null) return false;

    if(root.left == null && root.right == null && sum - root.val == 0) return true;

    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

113. Path SumII

https://leetcode.com/problems/path-sum-ii/

第一次写成的版本比较糙。当前节点不满足进行下一轮左右节点递归时，都加上了add和remove方法，这是传统回溯做多了的惯性，但实际上这两种情形加上删除的值是相同的，所以可以进行精简。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    dfs(root, sum, new ArrayList<>(), result);
    return result;
}

private void dfs(TreeNode node, int curSum, List<Integer> curList, List<List<Integer>> result) {
    if (node == null) {
        return;
    }
    if (curSum - node.val == 0 && node.left == null && node.right == null) {
        curList.add(node.val);
        result.add(new ArrayList<>(curList));
        curList.remove(curList.size() - 1);
        return;
    }
    curList.add(node.val);
    dfs(node.left, curSum - node.val, curList, result);
    curList.remove(curList.size() - 1);

    curList.add(node.val);
    dfs(node.right, curSum - node.val, curList, result);
    curList.remove(curList.size() - 1);
}

clean version:

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    dfs(root, sum, new ArrayList<>(), result);
    return result;
}

private void dfs(TreeNode node, int curSum, List<Integer> curList, List<List<Integer>> result) {
    if (node == null) {
        return;
    }
    curList.add(node.val);
    if (curSum - node.val == 0 && node.left == null && node.right == null) {
        result.add(new ArrayList<>(curList));
        curList.remove(curList.size() - 1);
        return;
    }
    dfs(node.left, curSum - node.val, curList, result);
    dfs(node.right, curSum - node.val, curList, result);

    curList.remove(curList.size() - 1);
}

Next Post

[Leetcode单排] 二叉树的序列化与反序列化 (N297)
Previous Post

[Leetcode单排] 树相关Easy题 (N100 N101 N104 N110 N111 N572 N965)

CATALOG

1. 102. Binary Tree Level Order Traversal
2. 107. Binary Tree Level Order Traversal II
3. 429. N-ary Tree Level Order Traversal
4. 872. Leaf-Similar Trees
5. 112. Path Sum
6. 113. Path SumII

